package com.zhanghp.class038;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * O(n! * n)<br/>
 * 时间复杂度原理：一共有n个数的话，来到第0个位置有n种，1索引位置有n-1 .... n索引位置有1种<br/>
 * 排列的个数：n!<br/>
 * 生成所有排列：n长度<br/>
 * 时间复杂度：O (n! * n) = O (n!)<br/>
 * <p>
 * 没有重复项数字的全排列<br/>
 * 测试链接 : https://leetcode.cn/problems/permutations/<br/>
 *
 * @author zhanghp
 * @since 2024/6/20 10:55
 */
public class Code03_Permutations {

    public static void main(String[] args) {
        int[] a = new int[]{1,2,3};
        List<List<Integer>> permute = permute(a);
        for (List<Integer> it : permute) {
            System.out.println(Arrays.toString(it.toArray()));
        }
    }

    public static List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        f(nums, 0, ans);
        return ans;
    }

    /**
     * 当前cur，到之后交换并记录<br/>
     * cur + 1, 从cur+1。。。nums.length 交换并记录<br/>
     * 。。。
     *
     * @param num
     * @param cur
     * @param ans
     */
    public static void f(int[] num, int cur, List<List<Integer>> ans) {
        if (cur == num.length) {
            // 因为num空间利用，所以当cur达到长度，则全放
            List<Integer> list = new ArrayList<>();
            for (int a : num) {
                list.add(a);
            }
            ans.add(list);
        } else {
            // 当前cur 和 当前位置及后面的索引挨个换位置
            for (int changeIndex = cur; changeIndex < num.length; changeIndex++) {
                swap(num, cur, changeIndex);
                f(num, cur + 1, ans);
                // 清理现场（什么时候清理现场？若要保留状态继续处理,则清理现场)
                // 如果是基本类型，就不用，因为是拷贝了一份数值，传参的原数值不会被改变
                swap(num, cur, changeIndex);
            }
        }
    }

    public static void swap(int[] arr, int a, int b) {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }

}
